% Define document
\documentclass[11pt]{scrartcl}

% Import packages
\usepackage[dutch,english]{babel}
\usepackage{graphicx}
\usepackage{caption}
\usepackage{listings}
\usepackage{parskip} % split paragraphs by vertical space
\usepackage{amsfonts}
\usepackage{mathtools}
\usepackage{gensymb}
\usepackage{tabularx} % for multicolumns

\usepackage{tikz} 
\usetikzlibrary{calc,intersections,through,backgrounds}


% Begin document
\begin{document}
\selectlanguage{dutch}



%Add title
\title{Oefeningen TAI: \\
Oefenzitting 2: Groepen}
\date{}
\maketitle


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% About
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{About}
Uitwerking van oefenziting 2 van Toepassingen van Algebra in Informatica gedoceerd in de 3e Bachelor Informatica aan de KULeuven in 2012.

Latex code van dit document te vinden op:\\
SVN checkout: \texttt{https://oefenzittingen-tai.googlecode.com/svn/trunk/}\\
Google code: \texttt{https://code.google.com/p/oefenzittingen-tai/}

Credits: Peter Roelants, Wouter Schaekers
%TODO: put your name here

Te gebruiken op eigen risico!




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Oef 1 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Opgave 1}
Bewijs dat $\mathbb{R}_0 \times \mathbb{R}$ voorzien van de samenstellingswet $((a,b),(c,d)) \mapsto (ac, bc + d)$ een groep is. Is hij abels?



\subsection*{oplossing 1}
Groepen: p. 93 eerste deel cursus, p. 1 tweede deel cursus.

Abels: abels komt overeen met commutatief, een groep is abels als de samenstellingswet commutatief is: p. 94 eerste deel cursus, p. 1 tweede deel cursus.

Is $<A,*>$ een groep?

\begin{itemize}
  \item 
  Closure ($*$ overal bepaald?): $ac \in \mathbb{R}_0$ en $bc + d \in \mathbb{R} \Rightarrow$ OK.
  
  
  \item
  $*$ Associatief? \\
  \begin{center}
  $ ((a,b)*(c,d))*(e,f) = (ac, bc + d)*(e,f) = (ace, (bc + d)e + f) = (ace, bce + de + f)  $\\
  $=$ \\
  $ (a,b)*((c,d)*(e,f)) = (a,b)*(ce,de+f) = (ace, bce + (de + f)) = (ace, bce + de + f) $\\
  \end{center}
  $ \Rightarrow $ OK
  
  
  \item
  $\exists$ neutraal element?\\
  $(a,b) * (1,0) = (a,b) = (1,0) * (a,b)$\\
  $\Rightarrow$ neutraal elementen = $(1, 0)$ $\Rightarrow$ OK
  
  
  
  \item
  Elk element van $A$ heeft inverse t.o.v. $*$?\\
  $(a, b) * (\frac{1}{a}, \frac{-b}{a}) = (1, 0)$\\
  $\Rightarrow (a, b)^{-1} = (\frac{1}{a}, \frac{-b}{a}) \Rightarrow$ OK
\end{itemize}
$\Rightarrow$ $<A,*>$ is een groep.

Is $<A,*>$ een abels?\\
$(a,b) * (c,d) = (ac, bc + d) \neq (ca, da + b) = (c,d) * (a,b)$\\
('maal' en 'plus' mixen geeft niet-commutatieve bewerkingen)\\
$Rightarrow$ $<A,*>$  is niet abels.





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Oef 2
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Opgave 2}
$<S_n, \circ>$ is de groep van de permutaties van een verzameling van n elementen. Stel de samenstellingstabel op voor $<S_3, \circ>$. Zijn er deelgroepen? Normaaldelers?


\subsection*{oplossing 2}
Permutaties: p.56 eerste deel cursus.\\
Samenstellingstabel = bewerkingstabel: p.80 eerste deel cursus.\\
Deelgroepen: p.94 eerste deel cursus, p.2 tweede deel cursus.\\
Normaaldelers: p.103 eerste deel cursus, p.2 tweede deel cursus.

permutaties $S_3$ = $\{ 123, 132, 213, 231, 312, 321 \}$

%tabel
\begin{table}[h!]
\centering
\begin{tabular}{ | c || c | c | c | c | c | c | }
	\hline
	$\circ$	&	$123$ &	$132$ &	$213$ &	$231$ &	$312$ &	$321$\\
  	\hline
  	\hline
    $123$	&	$123$ &	$132$ &	$213$ &	$231$ &	$312$ &	$321$\\
    \hline         
	$132$	&	$132$ &	$123$ &	$231$ &	$213$ &	$321$ &	$312$\\
	\hline  
	$213$	&	$213$ &	$312$ &	$123$ &	$321$ &	$132$ &	$231$\\
	\hline  
	$231$	&	$231$ &	$321$ &	$132$ &	$312$ &	$123$ &	$213$\\
	\hline  
	$312$	&	$312$ &	$213$ &	$321$ &	$123$ &	$213$ &	$132$\\
	\hline  
	$321$	&	$321$ &	$231$ &	$312$ &	$132$ &	$213$ &	$123$\\
  	\hline  
\end{tabular}
\end{table}

Deelgroepen:\\
$\{ 123, 132 \}$,\\
$\{ 123, 213 \}$,\\
$\{ 123, 321 \}$,\\
$\{ 123, 231, 312\}$

Normaaldelers:\\
$\{ 123, 312, 231 \}$







%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Oef 3
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Opgave 3}
Zoek de generatoren van de additieve cyclische groepen $\mathbb{Z}_{10}, \mathbb{Z}_{11}, \mathbb{Z}_{12}$.


\subsection*{oplossing 3}
Cyclische groep: p.97 eerst deel cursus, p.1 tweede deel cursus.\\


$\mathbb{Z}_{10} = \overline{1}, \overline{3}, \overline{7}, \overline{9}$ $\pmod{10}$

$\mathbb{Z}_{11} = \overline{1}, \overline{2}, \overline{3}, \overline{4}, \overline{5}, \overline{5},
 \overline{7}, \overline{8}, \overline{9}, \overline{10}$ $\pmod{11}$
 
$\mathbb{Z}_{12} = \overline{1}, \overline{5}, \overline{7}, \overline{11}$ $\pmod{12}$

$\rightarrow$ generators mogen geen gemeenschappelijke deler hebben met $n$
 uit $\mathbb{Z}_{n}$.
 
 
 
 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Oef 4
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Opgave 4}
Genereer de groep voortgebracht onder vermenigvuldiging door de matrices\\

\begin{center}
$
\begin{bmatrix}
       0 	& 1\\
       -1 	& 0 
\end{bmatrix}
$
en
$
\begin{bmatrix}
       0 	& 1\\
       1 	& 0 
\end{bmatrix}
$
\end{center}

Bewijs dat dit een niet-abelse groep is van orde 8.



\subsection*{oplossing 4}
Orde groep = cardinaliteit van een groep: p.94 eerste deel cursus, p.1 tweede deel cursus.
Abels = groep heeft commutatieve samenstellingswet.


\begin{tabularx}{\textwidth}{XX}
$x = \begin{bmatrix}
       0 	& 1\\
       -1 	& 0 
\end{bmatrix}$

$\Rightarrow$

$x^1 = \begin{bmatrix}
       0 	& 1\\
       -1 	& 0 
\end{bmatrix}$

$x^2 = \begin{bmatrix}
       -1 	& 0\\
       0 	& -1 
\end{bmatrix}$

$x^3 = \begin{bmatrix}
       0 	& -1\\
       1 	& 0 
\end{bmatrix}$

$x^4 = \begin{bmatrix}
       1 	& 0\\
       0 	& 1 
\end{bmatrix}$

&

$y = \begin{bmatrix}
       0 	& 1\\
       1 	& 0 
\end{bmatrix}$

$\Rightarrow$

$y^1 = \begin{bmatrix}
       0 	& 1\\
       1 	& 0 
\end{bmatrix}$

$y^2 = \begin{bmatrix}
       1 	& 0\\
       0 	& 1 
\end{bmatrix}$
\end{tabularx}


\begin{tabularx}{\textwidth}{XX}
$x \times y = \begin{bmatrix}
       1 	& 0\\
       0 	& -1 
\end{bmatrix}$

$x^2 \times y = \begin{bmatrix}
       0 	& -1\\
       -1 	& 0 
\end{bmatrix}$
&

$x^3 \times y = \begin{bmatrix}
       -1 	& 0\\
       0 	& 1 
\end{bmatrix}$
\end{tabularx}

$\Rightarrow$ 8 verschillende elementen $\Rightarrow$ groep van orde 8.


Abels?
$x \times y = 
\begin{bmatrix}
       1 	& 0\\
       0 	& -1 
\end{bmatrix}
\neq
\begin{bmatrix}
       -1 	& 0\\
       0 	& 1 
\end{bmatrix}
= y \times x
$

$\Rightarrow$ de groep is niet abels.

\vspace{1cm}
Merk op: $\begin{bmatrix}
       0 	& 1\\
       -1 	& 0 
\end{bmatrix}$ is de spiegel-matrix langs de y-as, $\begin{bmatrix}
       0 	& 1\\
       1 	& 0 
\end{bmatrix}$ is de spigel-matrix langs $y=x$.





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Oef 5
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Opgave 5}
Beschouw de groep $G = <\mathbb{Z}_{7}/\{0\}, \bullet>$ van de gehele getallen modulo 7 zonder nul en met de vermenigvuldiging modulo 7. Bepaal de orde van al de elementen. Is de groep commutatief?


\subsection*{oplossing 5}

$1$: $(1^1 = 1)$ $\Rightarrow$ orde = 1

$2$: $(2^1 = 2)$, $(2^2 = 4)$, $(2^3 = 1)$  $\Rightarrow$ orde = 3

$3$: $(3^1 = 3)$, $(3^2 = 2)$, $(3^3 = 6)$, $(3^4 = 4)$, $(3^5 = 5)$, $(3^6 = 1)$ $\Rightarrow$ orde = 6

$4$: $(4^1 = 4)$, $(4^2 = 2)$, $(4^3 = 1)$ $\Rightarrow$ orde = 3

$5$: $(5^1 = 5)$, $(5^2 = 4)$, $(5^3 = 6)$, $(5^4 = 2)$, $(5^5 = 3)$, $(5^6 = 1)$ $\Rightarrow$ orde = 6

$6$: $(6^1 = 6)$, $(6^2 = 1)$  $\Rightarrow$ orde = 2

De groep is commutatief, want de vermenigvuldiging is commutatief.





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Oef 6
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Opgave 6}
Bewijs dat elke deelgroep van een cyclische groep cyclisch is.


\subsection*{oplossing 6}
Cyclische groep $G$ $\rightarrow$ orde $n$ met generator $g$.

$G = \{ g^0, g^1, g^2, \ldots , g^{n-1}, g^n = g^0 \}$ $\rightarrow$ orde $n$.

$g^i$ met $i$ een deler van $n$ vormt een subgroep van $G$. Als $i$ geen deler is van $n$, dan is $g^i = G$, anders is $g^i$ een subgroep $\neq G$.

Stel $X$ een deelgroep van $G$.

Te bewijzen: $X$ is een cyclische groep.

Bewijs: Stel $X$ de deelgroep die $x$ bevat en niet cyclisch is $\Rightarrow$ $X$ is geen groep want het voldoet niet aan 'closure' (samenstellingswet overal bepaald) want anders is $x^i \in X$. En is dus geen deelgroep.




 
\end{document}
